/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package pathfinder;

import java.io.*;
import java.util.ArrayList;
import java.util.*;
import java.net.URL;

/**
 *
 * @author Christian Aastrup
 */
public class Pathfinder {
    
private Tile[][] arrayTiles2D;
private PathfinderTile[][] arrayPFTiles2D;
private static byte DIRECTION_NORTH = 1;
private static byte DIRECTION_EAST = 2;
private static byte DIRECTION_SOUTH = 4;
private static byte DIRECTION_WEST = 8;

    public Pathfinder()
    {
        setTileTraversabilityFromFile("traversability.txt");
        //setTileTraversability();
        setPathFinderTielTraversability();
        //outputTraversability();
        //debugArrayListChecker();
        //calculateOptimalPaths();
        calculateOptimalPathsBetter();
        //compareTileDirections();
        //debugTestExecutionTimeOfContainsAndByte();
    }
    
    public Tile[][] getTilesWithTraversability()
    {
        return arrayTiles2D;
    }
    
    private void compareTileDirections()
    {
        System.out.println("Direction for 0,0 to 1,1 " + arrayTiles2D[0][0].getDirectionForDestination(1,1));
        System.out.println("Direction for 1,10 to 1,1 " + arrayTiles2D[10][1].getDirectionForDestination(1,1));
        System.out.println("Direction for 2,1 to 1,1 " + arrayTiles2D[1][2].getDirectionForDestination(1,1));
        //arrayTiles2D[14][14].outputDirectionArray();
        //arrayTiles2D[2][1].outputDirectionArray();
        //arrayTiles2D[2][1].outputDirectionArray();
    }
    
    private void setPathFinderTielTraversability()
    {
        arrayPFTiles2D = new PathfinderTile[arrayTiles2D.length][arrayTiles2D[0].length];
        
        for(int i = 0; i < arrayTiles2D.length; i++)
        {       
            
            for(int n = 0; n < arrayTiles2D[i].length; n++)
            {
                if(arrayTiles2D[i][n].isTraversable() == true)
                {
                    arrayPFTiles2D[i][n] = new PathfinderTile(true);
                }
                
                else
                {
                    arrayPFTiles2D[i][n] = new PathfinderTile(false);
                }
            }
            
        }
    }
    
    private void setTileTraversabilityFromFile(String fileName)
    {
        ArrayList<String> alTraversabilityInString = new ArrayList<String>();
        
        try
		{
                    URL url = getClass().getResource( fileName);
                    
            
		    // open stream
                    //InputStream resStream = Pathfinder.class.getClass().getResourceAsStream(fileName);
		    //fileInputStreamWithTraversability = new FileInputStream(fileName);

		    //DataInputStream inputstream = new DataInputStream(fileInputStreamWithTraversability);
                    //BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(resStream));
                    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader( url.openStream() ) );
                    String line;
                    //read file
                    while ((line = bufferedReader.readLine()) != null)   
                    {
                        alTraversabilityInString.add(line);
                    }

		    // close
		    //fileInputStreamWithTraversability.close();		
		}

		catch (Exception e)
		{
			System.err.println ("unable to read file");
		}
        
        arrayTiles2D = new Tile[alTraversabilityInString.size()][alTraversabilityInString.size()];
        
        for(int y = 0; y < alTraversabilityInString.size(); y++)
        {
            //System.out.println("");
            for(int n = 0, x = 0; n < alTraversabilityInString.get(y).length() - 1; n += 3, x++)
            {
                //String s = alTraversabilityInString.get(i).;
                String s = alTraversabilityInString.get(y).substring(n, n+2);
                //System.out.print(s);
                
                if(s.equals("RR"))
                {
                    arrayTiles2D[x][y] = new Tile(true, arrayTiles2D.length, arrayTiles2D[0].length);
                }
                else if(s.equals("00"))
                {
                    arrayTiles2D[x][y] = new Tile(false, arrayTiles2D.length, arrayTiles2D[0].length);
                }
                else
                {
                    assert false : "Traversability file not formatted correctly";
                    System.out.println("Traversability file not formatted correctly");
                }
            }
        }
    }
    
    
    
    private void outputTraversability()
    {
        System.out.println("Output Traversability: ");
        System.out.print(" " + arrayTiles2D[0][0].isTraversable());
        System.out.print(" " + arrayTiles2D[0][1].isTraversable());
        System.out.print(" " + arrayTiles2D[0][2].isTraversable());
        System.out.print(" " + arrayTiles2D[0][3].isTraversable());
        System.out.print(" " + arrayTiles2D[0][4].isTraversable());
        System.out.print(" " + arrayTiles2D[0][5].isTraversable());
        System.out.print(" " + arrayTiles2D[0][6].isTraversable());
        System.out.print(" " + arrayTiles2D[0][7].isTraversable());
        System.out.print(" " + arrayTiles2D[0][8].isTraversable());
        System.out.print(" " + arrayTiles2D[0][9].isTraversable());
        System.out.print(" " + arrayTiles2D[0][10].isTraversable());
        System.out.print(" " + arrayTiles2D[0][11].isTraversable());
        System.out.print(" " + arrayTiles2D[0][12].isTraversable());
        System.out.print(" " + arrayTiles2D[0][13].isTraversable());
        System.out.println(" " + arrayTiles2D[0][14].isTraversable());
        
        
        
        
        for(int border = 0; border < arrayTiles2D.length; border++)
        {
            System.out.print("#");
        }
        System.out.println("##");
        
        for(int y = 0; y < arrayTiles2D.length; y++)
        {
            System.out.print("#");
            for(int x = 0; x < arrayTiles2D[y].length; x++)
            {
                if(arrayTiles2D[x][y].isTraversable())
                {
                    System.out.print("O");
                }
                else
                {
                    System.out.print("#");
                }
            }
            System.out.println("#");
           
            
        }
        for(int border = 0; border < arrayTiles2D.length; border++)
        {
            System.out.print("#");
        }
        System.out.println("##");
    }
    
    
    
    
    
    private boolean byteContainsNorth(int by)
    {
        if(by == 15 || by == 13 || by == 11 || by == 9 || by == 7 || by == 5 || by == 3 || by == 1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private boolean byteContainsEast(int by)
    {
        if(by == 15 || by == 14 || by == 11 || by == 10 || by == 7 || by == 6 || by == 3 ||  by == 2)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private boolean byteContainsSouth(int by)
    {
        if(by == 15 || by == 14 || by == 13 || by == 12 || by == 7 || by == 6 || by == 5 || by == 4)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private boolean byteContainsWest(int by)
    {
        if(by == 15 || by == 14 || by == 13 || by == 12 || by == 11 || by == 10 || by == 9 ||  by == 8)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private void doPrePathing()
    {
        
    }
    
    private void calculateOptimalPathsBetter()
    {
        int numberOfRows = arrayPFTiles2D.length;
        int numberOfColumns = arrayPFTiles2D[0].length;
        byte[][] prePathingArray2D = new byte[numberOfRows][numberOfColumns]; 
        int numberOfTiles = 1;
        int numberOfDestinationTiles = 1;
        
        //PRE PATHING init
        for(int prePathingY = 0; prePathingY < numberOfColumns; prePathingY++)
        {
           for(int prePathingX = 0; prePathingX < numberOfRows; prePathingX++)
           {
               prePathingArray2D[prePathingX][prePathingY] = 0;
           }
                    
        }
        
        System.out.println("prepathing sizes: " + numberOfColumns + " and " + numberOfRows);
        // PRE PATHING
        for(int prePathingY = 0; prePathingY < numberOfColumns; prePathingY++)
        {
           for(int prePathingX = 0; prePathingX < numberOfRows; prePathingX++)
           {              
               if(prePathingY == 0) // can not move NORTH because the north tile is outside board
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_NORTH;
               }
               if(prePathingY == numberOfColumns - 1) // can not move SOUTH because tile is outside board
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_SOUTH;
               }
               
               if(prePathingX == 0) // can not move WEST
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_WEST;
               }
               
               if(prePathingX == numberOfRows - 1) // can not move EAST
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_EAST;
               }
               
               if(!(arrayTiles2D[prePathingX][prePathingY].isTraversable())) // if current tile is not traversable
               {
                   //north
                    if(!(prePathingY == 0)) // make sure there is a north tile
                    {
                        prePathingArray2D[prePathingX][prePathingY - 1] += Pathfinder.DIRECTION_SOUTH;
                    }
                    
                   //east
                    if(!(prePathingX == numberOfRows - 1)) 
                    {
                        prePathingArray2D[prePathingX + 1][prePathingY] += Pathfinder.DIRECTION_WEST;
                    }
                    
                   //south
                    if(!(prePathingY == numberOfColumns - 1)) // make sure there is a south tile
                    {
                        prePathingArray2D[prePathingX][prePathingY + 1] += Pathfinder.DIRECTION_NORTH;
                    }
                   //west
                    if(!(prePathingX == 0)) // make sure there is a west tile
                    {
                        prePathingArray2D[prePathingX - 1][prePathingY] += Pathfinder.DIRECTION_EAST;
                    }
               }
               
               
               
               
           }
                    
        }

        
        byte[][] directionsNotValid = new byte[numberOfRows][numberOfColumns]; // create an array where the directions are not valid
        // happens when either the destination or the origin is not valid
        
        for(int dnvY = 0; dnvY < numberOfColumns; dnvY++)
        {
            for(int dnvX = 0; dnvX < numberOfRows; dnvX++)
            {
                directionsNotValid[dnvX][dnvY] = -1;
            }
        }
        
        for(int y = 0; y < numberOfColumns; y++) // Loop through all the (columns)tiles to find the optimal path
        {
            for(int x = 0; x < numberOfRows; x++) // Loop through all the rows to find the optimal path
            {
                if(arrayTiles2D[x][y].isTraversable() == false) // checks if the starting tile is even traversable
                {
                    //System.out.println("Tile: " + x + "," + y + " is not traversable, skipping");
                    arrayTiles2D[x][y].setDestinations(directionsNotValid);
                    continue;
                }
                long startTime1TileAllDests = System.currentTimeMillis();
                PathfinderTile startingPathFindertile = arrayPFTiles2D[x][y];
                byte[][] directionsToDestination = new byte[numberOfRows][numberOfColumns];
                
                for(int destinationY = 0; destinationY < numberOfColumns; destinationY++) // find the optimal path to all the tiles on the board for the current tile
                {
                    for(int destinationX = 0; destinationX < numberOfRows; destinationX++)
                    { 
                        long startTime1Tile1Dest = System.currentTimeMillis();
                        if(arrayTiles2D[destinationX][destinationY].isTraversable() == false)
                        {
                            directionsToDestination[destinationX][destinationY] = -1;
                            //System.out.println("Destination not traversable");
                            continue;
                        }
                        if(destinationX == x && destinationY == y) // if the destination is the same as the starting tile
                        {
                            directionsToDestination[destinationX][destinationY] = -1; // set all directions to -1
                            //System.out.println("Starting and destination tile same");
                            continue;
                            
                        }
                        
                        long startTime = System.currentTimeMillis();
                        
                        PathfinderTile destinationPathFindertile = arrayPFTiles2D[destinationX][destinationY]; // change later
                        PathfinderTile currentPathFindertile = startingPathFindertile;
                        int stepsInCurrentOptimalPath = 999999;
                        ArrayList<ArrayList> alArrayListsWithPathsWhichReachedDest = new ArrayList<ArrayList>();
                        byte firstDirection = 0;
                        boolean isUniquePathsLeft = true;
                        
                        byte[][] pathingArray2D = new byte[numberOfRows][numberOfColumns];
                        
                        
                        
                        
                    
                        
                        /*
                        for(int copyarrayY = 0; copyarrayY < prePathingArray2D[0].length; copyarrayY++)  // copies the array, the array must be copied
                        {
                            for(int copyarrayX = 0; copyarrayX < prePathingArray2D.length; copyarrayX++)
                            {
                                pathingArray2D[copyarrayX][copyarrayY] = prePathingArray2D[copyarrayX][copyarrayY];
                            }
                        }
                         * */
   
                        for(int n = 0; isUniquePathsLeft == true; n++) // Loop through all the paths for 1 tile and 1 destination
                        {
                            
                            //System.out.println("start; " + isUniquePathsLeft);
                            boolean deadEndFound = false;
                            boolean pathFound = false;
                            int currentPosX = x;
                            int currentPosY = y;
                            
                       
                       
                            ArrayList<PathfinderTile> alTraversedTiles = new ArrayList<PathfinderTile>();

                       
                            //variable change/methods
                            alTraversedTiles.add(arrayPFTiles2D[currentPosX][currentPosY]);
                            byte lastDirectionTraveled = 0;
                            //System.out.println("");
                            //System.out.println("new Path: ");
                       
                       for(int numberOfSteps = 0;deadEndFound == false && pathFound == false;) // loop through 1 path
                       {
                           assert (pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY]) < 16 : "ERROR: pathing at exceeded 15, a direction has been added more than"; // if has exceeded 15 then one direction has been added more than once
     
                           
                           
                           if(numberOfSteps > (stepsInCurrentOptimalPath - 2)) // check if number of steps we've taken has exceeded the number of steps in the current best path that has reached dest
                           {
                               if(lastDirectionTraveled == Pathfinder.DIRECTION_NORTH)
                                    {
                                        //alPrePathingArray.get(currentPosX * numberOfColumns + currentPosY)
                                        //alCurrentPathing.set()
                                        pathingArray2D[currentPosX][currentPosY + 1] += Pathfinder.DIRECTION_NORTH;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_EAST)
                                    {
                                        pathingArray2D[currentPosX - 1][currentPosY] += Pathfinder.DIRECTION_EAST;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_SOUTH)
                                    {
                                        pathingArray2D[currentPosX][currentPosY - 1] += Pathfinder.DIRECTION_SOUTH;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_WEST)
                                    {
                                        pathingArray2D[currentPosX + 1][currentPosY] += Pathfinder.DIRECTION_WEST;
                                    }
                               
                                    else if(lastDirectionTraveled == 0)
                                    {
                                        //System.out.println("Test");
                                        assert currentPosX == x && currentPosY == y : "PATHING ERROR: no direction and current position not 0,0";
                                        long executionTime = System.currentTimeMillis() - startTime;
                                        //System.out.println("direction == 0, pathing done, " + currentPosX + "," + currentPosY + " to " + destinationX + "," + destinationY +  " EXECUTION TIME: " + executionTime + " ms");
                                        isUniquePathsLeft = false;
                                        deadEndFound = true;
                                        continue;

                                    }
                                    
                               deadEndFound = true;
                               continue;
                           }

                           
                           

                            // try to move NORTH
                           boolean isNorthAvailable = !(byteContainsNorth( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY] ));
                            if(isNorthAvailable) // checks if the north tile is available
                            {
                                PathfinderTile northTile = arrayPFTiles2D[currentPosX][currentPosY - 1];
                                if(alTraversedTiles.contains( northTile ) == false ) // check if has traversed this tile this turn
                                {
                                    //System.out.println("Moved North, steps: " + numberOfSteps + " position: " + currentPosX + "," + currentPosY);
          
                                    currentPosY -= 1;        
                                    numberOfSteps++;
                                    lastDirectionTraveled = Pathfinder.DIRECTION_NORTH;
                                    
                                    currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                    alTraversedTiles.add(currentPathFindertile);
                                    
                                    if(numberOfSteps == 1)
                                    {
                                        firstDirection = lastDirectionTraveled;
                                    }
                                    
                                    if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                    {
                                        pathFound = true;
                                        alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);
                                        
                                        
                                        if(alTraversedTiles.size() < stepsInCurrentOptimalPath)
                                        {
                                            stepsInCurrentOptimalPath = alTraversedTiles.size()- 1;
                                        }
                                        
                                        //System.out.println("Path Found, Steps: " + (alTraversedTiles.size() -1) + " Optimal path: " + stepsInCurrentOptimalPath);
                                        
                                        //make sure this path is closed off i.e. make it a dead end

                                        pathingArray2D[currentPosX][currentPosY + 1] += Pathfinder.DIRECTION_NORTH;
                                        
                                    }
                                    
                                    continue;
                                     
                                }
                                // if unable to move it is because the tile has already been traversed this turn
                                // since contains method takes more than than the intContainsXX method, make North unavailable
                                else 
                                    {
                                        pathingArray2D[currentPosX][currentPosY] += Pathfinder.DIRECTION_NORTH;
                                        continue;
                                    }
                            }
                                
                                   
                            
                             //try to move EAST
                            boolean isEastAvailable = !(byteContainsEast( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY] ));
                            if(isEastAvailable) // checks if allowed to move to the east tile
                            {
                                PathfinderTile eastTile = arrayPFTiles2D[currentPosX + 1][currentPosY];
                                
                                if(alTraversedTiles.contains( eastTile ) == false ) // check if has traversed this tile this turn
                                {
                                    //System.out.println("Moved East, steps: " + numberOfSteps + " position: " + currentPosX + "," + currentPosY);
                                    //System.out.println("Tiles not avail: " + alPathsWhichAreDeadEnds.get(numberOfSteps));

                                    currentPosX += 1;        // updates the position in the array
                                    numberOfSteps++;                    // 
                                    lastDirectionTraveled = 2;
                                    
                                    currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                    alTraversedTiles.add(currentPathFindertile);
                                    
                                    if(numberOfSteps == 1)
                                    {
                                        firstDirection = lastDirectionTraveled;
                                    }
                                    
                                    if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                    {
                                        pathFound = true;
                                        alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);
     
                                        
                                        if(alTraversedTiles.size() < stepsInCurrentOptimalPath)
                                        {
                                            stepsInCurrentOptimalPath = alTraversedTiles.size() - 1;
                                        }
                                        //System.out.println("Path Found, Steps: " + (alTraversedTiles.size() -1) +  " Optimal path: " + stepsInCurrentOptimalPath + "destination: ");
                                        
                                        //make sure this path is closed off i.e. make it a dead end
                                        pathingArray2D[currentPosX - 1][currentPosY] += Pathfinder.DIRECTION_EAST;
                                        
                                    }
                                    
                                    continue;
                                     
                                }
                                // if unable to move it is because the tile has already been traversed this turn
                                // since contains method takes more than than the intContainsXX method, make East unavailable
                                else // if unable to move east
                                    {
                                        pathingArray2D[currentPosX][currentPosY] += Pathfinder.DIRECTION_EAST;
                                        continue;
                                    }
                            }
   
                            
                            //try to move SOUTH
                            boolean isSouthAvailable = !(byteContainsSouth( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY]));
                            if(isSouthAvailable) // checks if allowed to move to the south tile
                            {
                                PathfinderTile southTile = arrayPFTiles2D[currentPosX][currentPosY + 1];
                                
                                if(alTraversedTiles.contains( southTile ) == false ) // check if has traversed this tile this turn
                                {
                                    //System.out.println("Moved South, steps: " + numberOfSteps + " position: " + currentPosX + "," + currentPosY);

                                    currentPosY += 1;        // updates the position in the array
                                    numberOfSteps++;                    // has taken one step
                                    lastDirectionTraveled = 4;
                                    
                                    if(numberOfSteps == 1)
                                    {
                                        firstDirection = lastDirectionTraveled;
                                    }
                                    
                                    currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                    alTraversedTiles.add(currentPathFindertile);
                                    
                                    if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                    {
                                        pathFound = true;
                                        alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);
                                       
                                        
                                        if(alTraversedTiles.size() < stepsInCurrentOptimalPath)
                                        {
                                            stepsInCurrentOptimalPath = alTraversedTiles.size() - 1;
                                        }
                                        //System.out.println("Path Found, Steps: " + (alTraversedTiles.size() -1) + " Optimal path: " + stepsInCurrentOptimalPath);
                                        
                                        //make sure this path is closed off i.e. make it a dead end
                                        pathingArray2D[currentPosX][currentPosY - 1] += Pathfinder.DIRECTION_SOUTH;
                                      
                                        
                                    }
                                    
                                    continue;
                                     
                                }
                                // if unable to move it is because the tile has already been traversed this turn
                                // since contains method takes more than than the intContainsXX method, make South unavailable
                                else 
                                    {
                                        pathingArray2D[currentPosX][currentPosY] += Pathfinder.DIRECTION_SOUTH;
                                        continue;
                                    }
                            }
                               
   
                            //try to move WEST
                            boolean isWestAvailable = !(byteContainsWest( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY] ));
                            if(isWestAvailable) // checks if allowed to move to the west tile
                            {
                                PathfinderTile westTile = arrayPFTiles2D[currentPosX - 1][currentPosY];
                                
                                if( alTraversedTiles.contains( westTile ) == false ) // check if has traversed this tile this turn
                                {
                                    //System.out.println("Moved West, steps: " + numberOfSteps+ " position: " + currentPosX + "," + currentPosY);

                                    currentPosX -= 1;        // updates the position in the array
                                    numberOfSteps++;                    // has taken one step
                                    lastDirectionTraveled = 8;
                                    
                                    if(numberOfSteps == 1)
                                    {
                                        firstDirection = lastDirectionTraveled;
                                    }
                                    
                                    currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                    alTraversedTiles.add(currentPathFindertile);
                                    
                                    if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                    {
                                        pathFound = true;
                                        alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);
                                        
                                        
                                        if(alTraversedTiles.size() < stepsInCurrentOptimalPath)
                                        {
                                            stepsInCurrentOptimalPath = alTraversedTiles.size() - 1;
                                        }
                                        //System.out.println("Path Found, Steps: " + (alTraversedTiles.size() -1) + " Optimal path: " + stepsInCurrentOptimalPath);
                                        
                                        //make sure this path is closed off i.e. make it a dead end
                                        numberOfSteps--;
                                        pathingArray2D[currentPosX + 1][currentPosY] += Pathfinder.DIRECTION_WEST;
                                        
                                    }
                                    
                                    continue;
                                     
                                }
                                // if unable to move it is because the tile has already been traversed this turn
                                // since contains method takes more than than the intContainsXX method, make West unavailable
                                else // if unable to move north and there is no northAvail string
                                    {
                                        pathingArray2D[currentPosX][currentPosY] += Pathfinder.DIRECTION_WEST;
                                        continue;
                                    }
                            }
                                
                                
      
                            //If can move nowhere = DEAD END
                           
                           // check if not allowed to move anywhere
                           if((pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY]) == 15) // checks if not allowed to move to any tiles because they dead ends
                                {
                                    //System.out.println("Dead End: currentPos: " + currentPosX + "," + currentPosY);
                                    if(currentPosX == x && currentPosY == y)
                                    {
                                        long executionTime = System.currentTimeMillis() - startTime;
                                        //System.out.println("pathing done, " + currentPosX + "," + currentPosY + " to " + destinationX + "," + destinationY +  " EXECUTION TIME: " + executionTime + " ms");
                                        
                                        isUniquePathsLeft = false;
                                        break;
                                    }
                                    //System.out.println("DEAD ENDsteps: " + numberOfSteps + "al total size: " + alPathsWhichAreDeadEnds.size() + " Al size == 4, last direction: " + lastDirectionTraveled + " current position: " + currentPosX + "," + currentPosY);
                                    if(lastDirectionTraveled == Pathfinder.DIRECTION_NORTH)
                                    {
                                        pathingArray2D[currentPosX][currentPosY + 1] += Pathfinder.DIRECTION_NORTH;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_EAST)
                                    {
                                        pathingArray2D[currentPosX - 1][currentPosY] += Pathfinder.DIRECTION_EAST;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_SOUTH)
                                    {
                                        pathingArray2D[currentPosX][currentPosY - 1] += Pathfinder.DIRECTION_SOUTH;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_WEST)
                                    {
                                        pathingArray2D[currentPosX + 1][currentPosY] += Pathfinder.DIRECTION_WEST;
                                    }
                                    
                                    
                                    
                                    deadEndFound = true;
                                    continue;
                                }
                            
                             
                            // this should never run
                            assert false : "End of loop encountered, pathing is defective";
                            System.out.println("Dead end, Current position: " + currentPosX + "," + currentPosY);
                            deadEndFound = true;
    
                           
                       } // and of the loop that goes through 1 path
                       
                      
                    } // end of isUniquePathsLeft loop (Loop that goes through all the paths)
                     
                     
                    //alArrayListsWithPathsWhichReachedDest.get(alArrayListsWithPathsWhichReachedDest.size() - 1);
                    //System.out.println("First direction: " + firstDirection);
                    directionsToDestination[destinationX][destinationY] = firstDirection;
                    //System.out.println("starting at: " + x + "," + y + " Destination: " + destinationX + "," + destinationY + " " + firstDirection + " and " + directionsToDestination[destinationX][destinationY]);
                    } // end of destination X loop
                   
                }
                
              arrayTiles2D[x][y].setDestinations(directionsToDestination);
              System.out.println("Execution for 1 tile to all dests: " + (System.currentTimeMillis() - startTime1TileAllDests));
            }
            
            
            
        }
        
        
        
       
    }
    
    

}
